"""
337. 打家劫舍 III
https://leetcode.cn/problems/house-robber-iii/description/

中等
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。
一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。 
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

 
示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
 

提示：

树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104
"""

from typing import List, Optional
from TreeNode import TreeNode
import math

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    """
    偷一个节点，则其父节点和子节点都不能偷。
    树的遍历算法：层次遍历，前序遍历，中序遍历，后序遍历。
    - 所有算法中都是左节点优先右节点
    - 层次遍历和前序遍历，父节点优先子节点
    - 中序遍历左子树优先父节点
    - 后序遍历，子节点优先父节点。
    
    暴力法：每个节点选或不选，2^n
    回溯法：回溯法是递归的最底层先解决，所以是后序遍历，左右子树有一个选，则当前节点不能选
        所以递归计算子节点可以被选的最大值，和子节点不可以被选（孙子节点可以被选）的最大值，求和比较即可
        但是会出现递归多次计算的情况，所以可以使用树形dp
    树形dp：
        递归过程记录当前节点被选的最大值和不被选的最大值
        每次返回两个状态，这样就不用递归两次了。
    """
    # 暴力回溯递归
    def rob(self, root: Optional[TreeNode]) -> int:
        # 递归终止条件
        if root is None: return 0
        # 偷当前节点
        if root.left:
            suml = self.rob(root.left.left) + self.rob(root.left.right)
        else:
            suml = 0
        if root.right:
            sumr = self.rob(root.right.left) + self.rob(root.right.right)
        else:
            sumr = 0
        sum1 = root.val + suml + sumr
        # 不偷当前节点
        sum2 = self.rob(root.left) + self.rob(root.right)
        return max(sum1, sum2)
    # 树形dp
    def rob(self, root: Optional[TreeNode]) -> int:
        sum1, sum2 = self.backtrack(root)
        return max(sum1, sum2)
    
    def backtrack(self, root: TreeNode):
        # 递归终止条件
        if root is None: return 0, 0

        suml1, suml2 = 0, 0
        sumr1, sumr2 = 0, 0
        if root.left:
            suml1, suml2 = self.backtrack(root.left)
        if root.right:
            sumr1, sumr2 = self.backtrack(root.right)
        # 偷当前节点（可偷可不偷）
        sum1 = root.val + suml2 + sumr2
        # 不偷当前节点
        sum2 = max(suml1, suml2)  + max(sumr1, sumr2)
        return sum1, sum2
    
    # 记忆递归，不用重复计算
    memory = {}
    def rob(self, root: TreeNode) -> int:
        if root is None:
            return 0
        if self.memory.get(root) is not None:
            return self.memory[root]
        # 偷父节点
        val1 = root.val
        if root.left:
            val1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val1 += self.rob(root.right.left) + self.rob(root.right.right)
        # 不偷父节点
        val2 = self.rob(root.left) + self.rob(root.right)
        self.memory[root] = max(val1, val2)
        # 偷或不偷的最大值
        return max(val1, val2)


if __name__ == "__main__":
    so = Solution()
    null = None
    root = [3,2,3,null,3,null,1]
    # root = [3,4,5,1,3,null,1]
    root = TreeNode.create_from_list(root)
    root.print()

    n = so.rob(root)
    print(n)